import java.util.ArrayList;
import java.util.List;

public class RecoverTree {

    List<TreeNode> list;
    List<TreeNode> temp;
    public void recoverTree1(TreeNode root) {
        list = new ArrayList<>();
        temp = new ArrayList<>();
        list.add(new TreeNode(Integer.MIN_VALUE));
        process1(root);
        int a = temp.get(0).val;
        temp.get(0).val = temp.get(temp.size() - 1).val;
        temp.get(temp.size() - 1).val = a;
    }

    public void process1(TreeNode node) {
        if (node == null) return;
        process(node.left);
        if (node.val < list.get(list.size() - 1).val) {
            temp.add(list.get(list.size() - 1));
            temp.add(node);
        }
        list.add(node);
        process1(node.right);
    }


    TreeNode pre = new TreeNode(Integer.MIN_VALUE);
    TreeNode l = null;
    TreeNode r = null;
    public void recoverTree(TreeNode root) {
        process(root);
        int temp = l.val;
        l.val = r.val;
        r.val = temp;
    }

    public void process(TreeNode node) {
        if (node == null) return;
        process(node.left);
        if (node.val < pre.val) {
            r = node;
            if (l == null) l = pre;
        }
        pre = node;
        process(node.right);
    }
}
